package com.learn.datastructures.search;

//注意：使用二分查找的前提是 该数组是有序的.
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr={13,67,89,100,501,508,1001};
        int searchIndex=BinarySearch.binarySearch(arr,0,arr.length-1,501);

        System.out.println(searchIndex);
    }

    /**
     * @param arr  数组
     * @param left 左边的索引
     * @param right 右边的索引
     * @param findVal 查找数
     * @return
     */
    public static int binarySearch(int[] arr,int left,int right,int findVal){

        // 当 left > right 时，说明递归整个数组，但是没有找到
        if(left>right){
            return -1;
        }

        int mid=(left+right)/2;
        int midVal=arr[mid];
        if(findVal<midVal){
            return binarySearch(arr,left,mid+1,findVal);
        }else if(findVal>midVal) {
            return binarySearch(arr,mid,right+1,findVal);
        }else{
            return mid;
        }
    }
}
